#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 

class Solution {
public:
    struct cmp
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        for (auto e : lists)
        {
            if (e)
                heap.push(e);
        }
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;

        while (!heap.empty())
        {
            ListNode* top = heap.top();
            heap.pop();
            prev->next = top;
            prev = prev->next;
            if (top->next)heap.push(top->next);
        }
        prev = ret->next;
        delete ret;
        return prev;
    }
};